//方法二 红黑树
#include<set>
#include<vector>
using namespace std;
class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int size=grid.size();
        if(size==0)return 0;
        multiset<vector<int>>u_set;
        for(int i=0;i<size;i++){
            u_set.insert(grid[i]);
        }
        int res=0;
        for(int i=0;i<size;i++){
            vector<int>col;
            for(int j=0;j<size;j++){
                col.push_back(grid[j][i]);
            }
            res+=u_set.count(col);
        }
        return res;
    }
};

//方法一 哈希表
#include<unordered_set>
using namespace std;
class Solution {
    struct hash_vector{
        size_t operator()(std::vector<int> const& vt) const {
            size_t seed = vt.size();
            for(auto& i : vt) 
                seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
            return seed;
        }
    };
    struct equal_to{
        bool operator()(const vector<int>&vt_1,const vector<int>&vt_2)const{
            int size=vt_1.size();
            for(int i=0;i<size;i++)
                if(vt_1[i]!=vt_2[i])
                    return false;
            return true;
        }
    };
public:
    int equalPairs(vector<vector<int>>& grid) {
        int size=grid.size();
        if(size==0)return 0;
        unordered_multiset<vector<int>,hash_vector,equal_to>u_set;
        for(int i=0;i<size;i++){
            u_set.insert(grid[i]);
        }
        int res=0;
        for(int i=0;i<size;i++){
            vector<int>col;
            for(int j=0;j<size;j++){
                col.push_back(grid[j][i]);
            }
            res+=u_set.count(col);
        }
        return res;
    }
};
